package codingforgreat.lchot150;

public class Lc033 {
    public int search(int[] nums, int target) {
        int L = 0;
        int R = nums.length - 1;
        int mid = 0;
        while(L <= R){
            mid = (L + R)/2;
            if(nums[mid] == target){
                return mid;
            }
            //nums[L] nums[mid] nums[R]
            if(nums[L] == nums[mid] && nums[mid] == nums[R]){
                while(L != mid && nums[L] == nums[mid]){
                    L++;
                }
                if(L == mid){
                    L = mid + 1;
                    continue;
                }
            }
            //nums[L] nums{mid} nums[R] 不全相等
            if(nums[L] != nums[mid]){
                if(nums[L] < nums[mid]){//L 到 mid 有序
                    if(target >= nums[L] && target <= nums[mid]){
                        R = mid - 1;
                    }else{
                        L = mid + 1;
                    }
                }else{
                    if(target > nums[mid] && target <= nums[R]){
                        L = mid + 1;
                    }else{
                        R = mid - 1;
                    }

                }
            }else{// [L] == [mid]
                if(nums[mid] < nums[R]){//mid - R 有序
                    if(target >= nums[mid] && target <= nums[R]){
                        L = mid + 1;
                    }else{
                        R = mid - 1;

                    }
                }else{
                    if(target >= nums[mid] && target <= nums[R]){
                        R = mid - 1;
                    }else{
                        L = mid + 1;
                    }
                }
            }

        }
        return -1;
    }
}
